W razie problemów technicznych ze Szkopułem, prosimy o kontakt mailowy pod adresem [email protected].
Jeśli chciałbyś porozmawiać o zadaniach, rozwiązaniach lub problemach technicznych, zapraszamy na serwery Discord. Są one moderowane przez społeczność, ale członkowie zespołu technicznego też są tam aktywni.
By a word we mean a sequence of capital letters of the English alphabet. The length of a word is the number of letters contained in it. This way, word ABAACBBBA is of length 9. By a block within a word we understand maximal consistent subsequence of the same letters. A word is called -hard, if it contains blocks. Taking into consideration the word , it turns out to be 6-hard, because it consists of the following blocks: A|B|AA|C|BBB|A.
If two given words are of the same length, it is possible to check how different they are. Two words of the length are -different, if for exactly positions (), 'th letter of the first word is different from 'th letter of the second word. Checking two words and AAAABBBBB, it turns out that they are 3-different.
For a given word , we want to find not too different word , so that it is not too complicated. Your task is to define, how simple can be.
Write a program which:
In the first line of the standard input there are two integers separated with a single space (, ). They represent adequately: the length of the word and the allowed level of difference. In the second line there are exactly capital letters forming the word .
One integer is to be written to the standard output - .
For the input data:
9 3 ABAACBBBA
the correct result is:
2
Task author: Tomasz Idziaszek.